1. Field of the Invention
The present invention relates in general to digital computer systems, and more particularly to cache memory systems.
2. Description of the Prior Art
Cache memories are used in many computer systems to improve system performance. A cache memory is a relatively small, fast memory which resides between a central processor and main system memory. Whenever the processor reads the contents of a memory location which is stored in the cache memory, the time required to access such location is drastically reduced. A good cache technique can provide a "hit ratio" of well over ninety percent, meaning that no main memory access is necessary for over ninety percent of the read operations performed. Access of data which is stored in the cache can improve access times by factors of three to ten times.
A cache performs functions requiring two different types of memory. The first type is the data memory, in which the data is actually stored. The second type is known as a tag memory, or tag RAM, which is used to determine which memory locations are actually stored in the cache. In general, the cache tag RAM contains a plurality of entries corresponding to the entries of the data cache. Each entry is indexed by some number of least significant bits of the address generated by the central processor, with the tag entry itself containing the most significant bits of the memory location which is stored in the corresponding data cache entry. If the most significant bits stored in the cache tag match the most significant bits of the address currently being generated, with the least significant bits of this address acting as an index to the tag RAM, a cache "hit" has occurred and the data to be read may be taken from the corresponding data cache entry. If data corresponding to the desired address is not located in the data cache, the tag entry will not match the most significant bits of the address, and a "miss" occurs. This indicates that the data must be retrieved from main system memory and placed into the data cache. At this time, the current contents of the cache tag entry are overwritten with the most significant bits of the newly retrieved address.
In multi-processor systems, it is possible to provide each processor in a system with its own cache memory. Each local processor accesses its own cache whenever possible, and accesses main system memory through a system bus only when necessary.
This situation introduces an important problem known as the "cache coherency problem." This problem arises whenever it is possible for shared variables in main system memory to be accessed by two or more processors in the system. These processors can be local central processing units, or input/output devices attached to the bus. The cache coherency problem arises when a single memory location is cached in two or more local caches. If one of the processors writes a new value into that memory location, it will be inconsistent with the value of the same variable, or main memory location, currently cached in the other caches. The cache coherency problem also arises when a non-caching device writes to a location in system memory which has been cached by another device.
One technique utilized in dealing with the cache coherency problem is to have all local processors having caches monitor, or "snoop," the main system bus at all times. If another processor or device writes data to a memory location which is currently stored in a local cache, the local cache entry is invalidated. If that location is later accessed by the local processor, the updated data is then retrieved from the main system memory.
Using a dual-port memory array in this manner, however, results in an area penalty on the tag RAM chip. This is because a dual-port memory, compared to a single-port memory array, can be two and a half to three and a half times larger, or more.
Therefore, it would be desirable to provide a cache tag memory which reduces space consumption as well as maintain the coherency of the cache memory.